<?php
/**
 * User: LRZ
 * Date: 2020/3/2
 * Time: 12:17
 */

/**
 *  383.赎金信
 *
 *  标签：字符串
 *
 *  给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。
 *  (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)
 *
 *  注意：你可以假设两个字符串均只含有小写字母。
 *
 *  canConstruct("a", "b") -> false
 *  canConstruct("aa", "ab") -> false
 *  canConstruct("aa", "aab") -> true
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/ransom-note
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$ransomNote = 'aa';
$magazine   = 'aab';
$res        = canConstruct($ransomNote, $magazine);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function canConstruct($ransomNote, $magazine)
{
    $rLength = strlen($ransomNote);
    $mLength = strlen($magazine);
    # 如果杂志字符串长度小于赎金信长度，则直接返回false
    if ($rLength > $mLength) {
        return false;
    }
    $mArray = [];
    for ($i = 0; $i < $mLength; $i++) {
        if (isset($mArray[$magazine[$i]])) {
            $mArray[$magazine[$i]]++;
        } else {
            $mArray[$magazine[$i]] = 1;
        }
    }
    for ($i = 0; $i < $rLength; $i++) {
        if ($mArray[$ransomNote[$i]]) {
            $mArray[$ransomNote[$i]]--;
        } else {
            return false;
        }
    }
    foreach ($mArray as $v) {
        if ($v < 0) {
            return false;
        }
    }
    return true;
}